package algorithms.roughgarden.part2.dynamicprogramming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

/**
 * Run with large heap size.
 * Successfully ran with 2048m
 * @author samurai
 *
 */
public class MainBig {
	private static final String INPUT_FILE_NAME = "knapsack_big.txt";
	private static final String DELIMITER=" ";
	//private static int[][] memoArray;
	private static int knapsackSize;
	private static int noOfItems;
	private static Map<Index, Integer> maxWeightMap = new HashMap<MainBig.Index, Integer>();
	private static int[] weightArray;
	private static int[] valueArray;

	public static void main(String[] args) throws IOException {
		InputStream is = Main.class.getResourceAsStream(INPUT_FILE_NAME);
		BufferedReader br = new BufferedReader(new InputStreamReader(is));
		String str;
		str = br.readLine();
		String[] strArr = str.split(DELIMITER);
		knapsackSize = Integer.parseInt(strArr[0]);
		noOfItems = Integer.parseInt(strArr[1]);
		weightArray = new int[noOfItems];
		valueArray = new int[noOfItems];
		//memoArray = new int[noOfItems+1][knapsackSize+1];
		int itemIdx=0 ;
		
		for(int i=0;i<knapsackSize;i++){
			maxWeightMap.put(new Index(0, i), 0);
		}
		while((str = br.readLine())!=null){
			strArr = str.split(DELIMITER);
			valueArray[itemIdx] = Integer.parseInt(strArr[0]);
			weightArray[itemIdx] = Integer.parseInt(strArr[1]);
			itemIdx++;
			
		}
		System.out.println(getOptimalSolutionForIndex(noOfItems, knapsackSize));
		//System.out.println(memoArray[noOfItems][knapsackSize]);
	}
	
	private static int temp;
	private static Integer getOptimalSolutionForIndex(int x, int y){
		if(x<=0 || y<=0){
			return 0;
		}
		//System.out.println("Calculating optimal solution for weight="+y+" , from first "+x+" items");
		Index idx = new Index(x,y);
		Integer maxWeight = maxWeightMap.get(idx);
		if(null == maxWeight){
			maxWeight = getOptimalSolutionForIndex(x-1,y);
			temp = weightArray[x-1];
			if(y>=weightArray[x-1]){
				maxWeight =  Math.max(maxWeight, valueArray[x-1]+getOptimalSolutionForIndex(x-1,y-temp));
			}
			maxWeightMap.put(idx, maxWeight);
		}
		return maxWeight;
	}

	private static final class Index{
		private int x;
		private int y;

		public Index(int x, int y){
			this.x = x;
			this.y = y;
		}

		@Override
		public int hashCode() {
			return x-y+(y<<5);
		}
		@Override
		public boolean equals(Object obj) {
			Index idx = (Index)obj;
			return idx.x == x &&
					idx.y == y;
		}


	}

}
